package LeetCode.BackTracking;

/**
 * @author : LdLtd
 * @Date : 2023/8/4
 * @Description:980.不同路径 III
 */
public class unique_paths_iii {
    //上右下左向量表示
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) {

    }

    class Solution {
        public int uniquePathsIII(int[][] grid) {
            int sx = -1, sy = -1, n = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 0) n++;
                    else if (grid[i][j] == 1) {
                        sx = i;
                        sy = j;
                        n++;
                    }
                }
            }
            return backtrack(grid, sx, sy, n);
        }

        private int backtrack(int[][] grid, int sx, int sy, int n) {
            if (grid[sx][sy] == 2) {
                return n == 0 ? 1 : 0;
            }
            int t = grid[sx][sy];
            //标记为已经走过
            grid[sx][sy] = -1;
            int res = 0;
            for (int i = 0; i < 4; i++) {
                int x = sx + dx[i];
                int y = sy + dy[i];
                if (x >= 0 && x < grid.length && y >= 0 && y < grid[x].length && grid[x][y] == 0 || grid[x][y] == 2) {
                    res += backtrack(grid, x, y, n - 1);
                }
            }
            //恢复现场
            grid[sx][sy] = t;
            return res;

        }
    }
}
